#!/usr/bin/env python
# -*- coding: utf-8 -*-

'''
@author: Tiago Barriga Nº 6048
'''
import time

######################################################
# classe  do tratamento dos nos
class Node:
    def __init__(self, key, valor):
        
        self.key = key
        self.valor = valor
        self.parent = None
        self.left   = None
        self.right  = None

        pass
    # metodo que devolve uma string com o nó
    def __str__(self):
        s = str(self.key) + ' : ' + str(self.valor)
        s += '('
        if self.parent == None:
            s += 'None'  + ', ' 
        else:
            s += str(self.parent.key) + ', ' 

        if self.left == None:
            s += 'None'  + ', ' 
        else:
            s += str(self.left.key) + ', ' 

        if self.right == None:
            s += 'None' + ')' 
        else:
            s += str(self.right.key) + ')' 
        return s
    
    def add_Node(self, x):
        pass
    
###########################################################
#### classe da arvore binaria 
#### cria arvore binarias e tratas as suas operações  
class ArvorePesquisaBinaria:
    #Definição do construtor da class Arvore Binária
    def __init__(self):
        self.root = None
        self.nil = None
    
    #Metodo insert, responsavel por adicionar nos a arvore
    def insert(self, z):
        y = None
        x = self.root
        while x != None:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    #Metodo search, permite procurar por um nó na arvore binária
    # @ param x, k (a partir de onde e o que)
    def search(self, x, k):
        if x == None or k == x.key:
            return x
        if k < x.key:
            return self.search(x.left, k)
        else:
            return self.search(x.right, k)
        
        
    #metetodo searchNeighbor, permite procurar por um vizinho na arvore binária
    def searchNeighbor(self, x, k):
        if x == self.nil or k == x.key:
            if x.left != self.nil:
                return x.left
            elif x.right != self.nil:
                return x.right
            else:
                return x.parent
        if k < x.key:
            return self.searchNeighbor(x.left, k)
        else:
            return self.searchNeighbor(x.right, k)
        pass
    #metodo minimum , devolve o nó que fica mais á esquerde da arvore
    def minimum(self, x):
        while x.left != None:
            x = x.left
        return x
    #metodo maximum, devolve o nó que fica mais á direita da arvore
    def maximum(self, x):
        while x.right != None:
            x = x.right
        return x
    #metodo sucessor, devolve o nó sucessor
    def sucessor(self, x):
        if x.right != None:
            return self.minimum(x.right)
        y = x.parent
        while y != None and x == y.right:
            x = y
            y = y.parent
        return y
    #metodo transplant, permite construir de novo uma arvore
    def transplant(self, u, v):
        if u.parent == None:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        if v != None:
            v.parent = u.parent
   #metodo delete, eliminação de um nó da arvore
    def delete(self, z):
        if z.left == None:
            self.transplant(z, z.right)
        elif z.right == None:
            self.transplant(z, z.left)
        else:
            y = self.minimum(z.right)
            if y.parent != z:
                self.transplant(y, y.right)
                y.right = z.right
                y.right.parent = y
            self.transplant(z, y)
            y.left = z.left
            y.left.parent = y
    
    #Metodo inorder_Walk, permite fazer a ordenação de uma lista
    def inorder_walk(self, x, lista):
        if x != None:
            self.inorder_walk(x.left, lista)
            lista.append( x )
            self.inorder_walk(x.right, lista)
            
    pass    

######################################################
    


######################################################
# classe de criação de KD-Tree's
class KDtree:
    def __init__(self, nElementos):
        
        self.nElementos = nElementos
        self.nos = [ Node(None, None) for k in range(nElementos) ]
        self.clear()
        self.pointer = Stack(nElementos)
        for k in range(0, nElementos):
            
            self.remove(k)
            pass
       
        pass
        self.next = [0 for k in range(nElementos)]
        self.key = [0 for k in range(nElementos)]
        
    # clear all tree
    def clear(self):
        self.NIL = None
        self.root = None
        self.head = None
        pass
    
    #Eliminação de nós da arvore
    # @ param no (o no pretendido eliminar)
    # retorna a sua posição
    def NodeRemove(self, no):
        if self.nos[no].left == self.NIL or self.nos[no].right == self.NIL:
            tmp = no
        else:
            tmp = self.tree_sucessor(no)
            pass
        if self.nos[tmp].left != self.NIL:
            x = self.nos[tmp].left
        else:
            x = self.nos[tmp].right
            pass
        if x != self.NIL:
            self.nos[x].parent = self.nos[tmp].parent
            pass
        if self.nos[tmp].parent == self.NIL:
            self.root = x
        elif tmp == self.nos[self.nos[tmp].parent].left:
            self.nos[self.nos[tmp].parent].left = x
        else:
            self.nos[self.nos[tmp].parent].right = x
            pass
        if tmp != no:
            self.nos[no].key = self.nos[tmp].key
            pass
        return tmp
      
        
    
    # metodo remove um no da arvore
    def remove(self, x):
        self.pointer.push(x)
        pass
    
    #alucação de espaço para um nó da arvore
    def malloc(self):
        x = self.pointer.pop()
        return x
            
    #inserção de nós na arvore
    def tree_insert(self, no):
        y = self.NIL
        x = self.root       
                
        while( x != self.NIL ):
            y = x
            if self.nos[no].key < self.nos[x].key:
                x = self.nos[x].left
            else:
                x = self.nos[x].right
                pass
            pass
        self.nos[no].parent = y
        if y == self.NIL:
            self.root = no
        elif self.nos[no].key < self.nos[y].key:
            self.nos[y].left = no
        else:
            self.nos[y].right = no
            pass
        pass
    
    
    #Este Metodo retorna uma string com a kdtree
    def __str__(self):
        t = '#############Kdtree##################'
        t += '\n'
        for k in xrange(self.nElementos):
            t += str(k) + ':' +" key: " + str(self.nos[k].key) + " p: " +\
                 str(self.nos[k].parent) + " valor: " +\
                 str(self.nos[k].valor) + " left: " +\
                 str(self.nos[k].left) + " right: " + \
                 str(self.nos[k].right) + '\n'
        return t
        pass
    pass


################################################
################## Stack #######################
################################################
class Stack:
        #Contrutor da classe
        def __init__(self, N):
                self.top = -1
                self.S = [0 for k in xrange(N)]
                pass
       
        ## Este Metodo stack_Empty verifica se a pilha esta vazia
        def stack_empty(self):
                if self.top < 0:
                        return True
                else:
                        return False
        ## Este metodo verifica se a pilha est� cheia
        def stack_full(self):
                if self.top >= len (self.S) -1:
                        return True
                else:
                        return False
                pass
               
        ##Metodo push
        def push(self, x):
                self.top += 1
                self.S[self.top] = x
                pass
        ##Metodo pop
        def pop(self):
                if self.stack_empty():
                        return "underflow"
                else:
                        self.top -= 1
                        return self.S[self.top + 1]
                pass
        ##Este metodo retorna uma string
        def __str__(self):
                s = ""
                s += str(self.top+1) + ": "
                for k in range(0, self.top+1):
                        s += ' ' + str(self.S[k])
                return s
        pass


        
def Main():
               
    N = 13 # dimensão da arvore
    listaKdTree = [(1, 1), (0, 1), (2, 2), (3, 2), (1,3), (4, 5), (7, 0), 
                   (2, 8), (9, 13), (13, 10), (10, 11), (9, 9) ]
    #Criação da lista com os dados
    nos = [None for k in range(12)]
    nos[0] = Node(listaKdTree[0], "Squall LionHeart")
    nos[1] = Node(listaKdTree[1], "Cloud Strife")
    nos[2] = Node(listaKdTree[2], "Erza Titania")
    nos[3] = Node(listaKdTree[3], "Ultimecia")
    nos[4] = Node(listaKdTree[4], "Alucard")
    nos[5] = Node(listaKdTree[5], "Ceras Victoria")
    nos[6] = Node(listaKdTree[6], "Renoa Heartilly")
    nos[7] = Node(listaKdTree[7], "Vicent Valentine")
    nos[8] = Node(listaKdTree[8], "Rurouni Kenshin")
    nos[9] = Node(listaKdTree[9], "Solid Snake")
    nos[10] = Node(listaKdTree[10], "Sephiroth")
    nos[11] = Node(listaKdTree[11], "Brandon Heat")
  
    #adicionar um nó
    arv = KDtree(N)
    
    for i in range(12):
        x = arv.malloc()
        arv.nos[x] = nos[i]
        arv.tree_insert(x)
        pass
           
    print arv
    print "############ Eliminação de um nó da kd-tree ############"       
    arv.remove(arv.NodeRemove(6))
    print arv
    
    

    pass
Main()